public class day6 {
    /**
     * 高精度乘法
     * NC10 大数乘法
     * https://www.nowcoder.com/practice/c4c488d4d40d4c4e9824c3650f7d5571?tpId=196&tqId=37177&ru=/exam/oj
     */
    public String solve (String s, String t) {
        // 将字符串进行翻转，之后对其进行拆分成一个一个字符串
        char[] ss = new StringBuffer(s).reverse().toString().toCharArray();
        char[] tt = new StringBuffer(t).reverse().toString().toCharArray();
        int m = ss.length;
        int n = tt.length;
        // 用来记录ss和tt的每一位 进行 无进位相乘相加后的值
        int[] arr = new int[m + n];
        // 1.无进位相乘相加
        for(int i = 0;i < m;i++) {
            // 固定ss 的位置的每一位的下标
            for(int j = 0;j < n;j++) {
                // 固定第一个值之后，和tt中的每一位都进行相乘，得到的值进行i和j位置之和的位置，存在重复的i和j相加后的下标值
                // 这说明这个位置是相乘后 需要进行相加的位置
                arr[i + j] += (ss[i] - '0') * (tt[j] - '0');
            }
        }

        // 2.把每一个位置的值留下一位，之后算 进位的值，进行往后计算
        // 相当于是进行 进位计算相加
        StringBuffer ret = new StringBuffer();
        int capity = 0,i = 0;
        while(i < arr.length - 1 || capity > 0) {
            int tmp = 0;
            if(i < arr.length - 1) {
                tmp += arr[i];
                i++;
            }
            tmp += capity;
            ret.append((char)tmp % 10);
            capity = tmp / 10;
        }

        // 3.对于后置0进行处理
        // 因为ret是返回值的翻转值，比如ret 为 101100 返回需要 001101 ，那么前面两个00需要进行删去，
        // 但是当整个ret只有一个0的时候不能删除
        while(ret.length() > 1 && ret.charAt(ret.length() - 1) == '0') {
            // 删除
            ret.deleteCharAt(ret.length() - 1);
        }
        // 4.返回需要进行翻转
        return ret.reverse().toString();
    }

    /**
     * 高精度加法
     * NC40 链表相加(二)
     * http://nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b?tpId=196&tqId=37147&ru=/exam/oj
     */
    public class ListNode {
        int val;
        ListNode next = null;
        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        // 将两个链表进行翻转
        ListNode h1 = reverse(head1);
        ListNode h2 = reverse(head2);
        ListNode cur1 = h1,cur2 = h2;
        ListNode ret = new ListNode(0);
        ListNode prev = ret;
        int capity = 0;
        while(cur1 != null || cur2 != null || capity > 0) {
            int tmp = 0;
            if(cur1 != null) {
                tmp += cur1.val;
                cur1 = cur1.next;
            }
            if(cur2 != null) {
                tmp += cur2.val;
                cur2 = cur2.next;
            }
            tmp += capity;
            ListNode cur = new ListNode(tmp % 10);
            prev.next = cur;
            prev = prev.next;
            capity = tmp / 10;
        }
        return reverse(ret.next);
    }

    public ListNode reverse(ListNode head) {
        // 使用 哨兵位 + 头插 进行完成 翻转操作
        ListNode newHead = new ListNode(0);
        ListNode cur = head;
        while(cur != null) {
            ListNode curN = cur.next;
            cur.next = newHead.next;
            newHead.next = cur;
            cur = curN;
        }
        return newHead.next;
    }


    /**
     * 高精度加法
     * NC1 大数加法
     * https://www.nowcoder.com/practice/11ae12e8c6fe48f883cad618c2e81475?tpId=196&tqId=37176&ru=/exam/oj
     */
    public String solve1 (String s, String t) {
        // write code here
        StringBuffer ret = new StringBuffer();
        int capity = 0; // 进位
        int i = s.length() - 1,j = t.length() - 1;
        while(i >= 0 || j >= 0 || capity > 0) {
            int tmp = 0;
            tmp += i >= 0 ? s.charAt(i--) - '0' : 0;
            tmp += j >= 0 ? t.charAt(j--) - '0' : 0;
            tmp += capity;
            ret.append((char)('0' + tmp % 10));
            capity = tmp / 10;
        }
        // 这样的到的字符串是反的
        // 比如 100 字符串那里是 001
        return ret.reverse().toString();
    }
}
